package com.algorithm.test;

import java.util.Stack;

public class BinaryTree {
    private Node root = null;

    BinaryTree() {

    }
    BinaryTree(int value) {
        root = new Node(value);
        root.leftChild  = null;
        root.rightChild = null;
    }
    public Node findKey(int value) {
        Node current = root;
        while (true) {
            if (value == current.value) {
                return current;
            } else if (value < current.value) {
                current = current.leftChild;
            } else if (value > current.value) {
                current = current.rightChild;
            }

            if (current == null) {
                return null;
            }
        }
    }
    public String insert(int value) {
        String error = null;

        Node node = new Node(value);
        if (root == null) {
            root = node;
            root.leftChild  = null;
            root.rightChild = null;
        } else {
            Node current = root;
            Node parent = null;
            while (true) {
                if (value < current.value) {
                    parent = current;
                    current = current.leftChild;
                    if (current == null) {
                        parent.leftChild = node;
                        break;
                    }
                } else if (value > current.value) {
                    parent = current;
                    current = current.rightChild;
                    if (current == null) {
                        parent.rightChild = node;
                        break;
                    }
                } else {
                    error = "having same value in binary tree";
                }
            } // end of while
        }
        return error;
    }
    /**
     * //中序遍历(递归)：
     *    1、调用自身来遍历节点的左子树
     *    2、访问这个节点
     *    3、调用自身来遍历节点的右子树
     */
    public void inOrderTraverse() {
        System.out.print("中序遍历:");
        inOrderTraverse(root);
        System.out.println();
    }

    private void inOrderTraverse(Node node) {
        if (node == null)
            return ;

        inOrderTraverse(node.leftChild);
        node.display();
        inOrderTraverse(node.rightChild);
    }
    /**
     * 中序非递归遍历：
     *     1）对于任意节点current，若该节点不为空则将该节点压栈，并将左子树节点置为current，重复此操作，直到current为空。
     *     2）若左子树为空，栈顶节点出栈，访问节点后将该节点的右子树置为current
     *     3) 重复1、2步操作，直到current为空且栈内节点为空。
     */
    public void inOrderByStack() {
        System.out.print("中序非递归遍历:");
        Stack<Node> stack = new Stack<Node>();
        Node current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.leftChild;
            }

            if (!stack.isEmpty()) {
                current = stack.pop();
                current.display();
                current = current.rightChild;
            }
        }
        System.out.println();
    }

    /**
     * 前序非递归遍历：
     *     1）对于任意节点current，若该节点不为空则访问该节点后再将节点压栈，并将左子树节点置为current，重复此操作，直到current为空。
     *     2）若左子树为空，栈顶节点出栈，将该节点的右子树置为current
     *     3) 重复1、2步操作，直到current为空且栈内节点为空。
     *     2	1	3	4	6	5	12	7	9	8	14	21	19
     *     2	1	3	4	6	5	12	7	9	8	14	21	19
     */
    public void preOrderByStack() {
        System.out.print("前序非递归遍历:");
        Stack<Node> stack = new Stack<Node>();
        Node current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current.display();
                current = current.leftChild;
            }

            if (!stack.isEmpty()) {
                Node temp = stack.pop();
                current = temp.rightChild;
            }
        }
        System.out.println();
    }

    public void backOrderByStack(){
        System.out.print("后序非递归遍历:");
        Stack<Node> stack = new Stack<Node>();
        Node current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.leftChild;
            }

            if (!stack.isEmpty()) {
                Node temp = stack.pop();
                if(temp.rightChild==null){
                    temp.display();
                }
                else{
                    current = temp.rightChild;
                }

            }
        }
        System.out.println();
    }
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        int[] arr = {2,3,4,1,6,5,12,7,9,8,14,21,19};
        for(int i :arr){
            tree.insert(i);
        }
//        tree.inOrderByStack();
        tree.preOrderByStack();
        tree.backOrderByStack();
    }








    class Node {
        int  value;
        Node leftChild;
        Node rightChild;

        Node(int value) {
            this.value = value;
        }

        public void display() {
            System.out.print(this.value + "\t");
        }

        @Override
        public String toString() {
            // TODO Auto-generated method stub
            return String.valueOf(value);
        }
    }


}
